package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/reverse-linked-list-ii/description/?envType=study-plan-v2&envId=top-interview-150/">反转链表 II(Reverse Linked List II)</a>
 * <p>给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。 </p>
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3,4,5], left = 2, right = 4
 *      输出：[1,4,3,2,5]
 *
 * 示例 2：
 *      输入：head = [5], left = 1, right = 1
 *      输出：[5]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *          <li>链表中节点数目为 n</li>
 *          <li>1 <= n <= 500</li>
 *          <li>-500 <= Node.val <= 500</li>
 *          <li>1 <= left <= right <= n</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/13 11:21
 */
public class LC0092ReverseLinkedList_II_M {

    static class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            if (head == null || head.next == null || left == right) {
                return head;
            }
            ListNode dummy = new ListNode(-1, head);
            // 找到left所在位置的前一个节点
            ListNode prevNode = dummy;
            for (int i = 1; i < left; i++) {
                prevNode = prevNode.next;
            }
            ListNode currNode = prevNode.next;
            ListNode nextNode;
            for (int i = left; i < right; i++) {
                nextNode = currNode.next;
                currNode.next = nextNode.next;
                nextNode.next = prevNode.next;
                prevNode.next = nextNode;
            }
            return dummy.next;
        }

        public ListNode reverseBetween2(ListNode head, int left, int right) {
            if (head == null || head.next == null || left == right) {
                return head;
            }
            // 找到left所在位置的前一个节点
            ListNode leftPrevNode = head;
            ListNode leftIndexNode;
            for (int i = 1; i < left - 1; i++) {
                leftPrevNode = leftPrevNode.next;
            }
            leftIndexNode = leftPrevNode.next;
            // 找到right所在位置的节点
            ListNode rightIndexNode = leftIndexNode;
            ListNode rightNextNode;
            for (int i = left; i < right; i++) {
                rightIndexNode = rightIndexNode.next;
            }
            rightNextNode = rightIndexNode.next;
            // 1.截断
            leftPrevNode.next = null;
            rightIndexNode.next = null;
            // 2.反转链表
            leftIndexNode = reserve(leftIndexNode);
            // 3.拼接
            leftPrevNode.next = leftIndexNode;
            while (leftIndexNode.next != null) {
                leftIndexNode = leftIndexNode.next;
            }
            leftIndexNode.next = rightNextNode;
            return head;
        }

        private ListNode reserve(ListNode node) {
            ListNode prevNode = null;
            ListNode currNode = node;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }
            return prevNode;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);

        ListNode head2 = new ListNode(5);
        Solution solution = new Solution();
        ListNode listNode = solution.reverseBetween(head1, 2, 4);
        while (listNode != null) {
            System.out.print(listNode.val);
            if (listNode.next != null) {
                System.out.print(" -> ");
            } else {
                System.out.println();
            }
            listNode = listNode.next;
        }
        listNode = solution.reverseBetween(head2, 1, 1);
        while (listNode != null) {
            System.out.print(listNode.val);
            if (listNode.next != null) {
                System.out.print(" -> ");
            } else {
                System.out.println();
            }
            listNode = listNode.next;
        }
    }
}
